package edu.bupt.e1btree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class T02BinaryTreeInorder {
    public List<Integer> inorderTraversal(TreeNode root) {

        ArrayList<Integer> integers = new ArrayList<Integer>();
        if (null == root) return integers;
        Stack<TreeNode> treeNodes = new Stack<TreeNode>();
        TreeNode p = root;

        while (!treeNodes.empty() || p!=null){
            if (null !=p ){
                treeNodes.push(p);
                p = p.left;
            }else {
                TreeNode pop = treeNodes.pop();
                integers.add(pop.val);
                p = p.right;
            }
        }
        return integers;
    }
}
